\section{Descripci\'on del Problema}
El problema radica en encontrar el camino que llegue en el 
menor tiempo posible  desde una ciudad de origen $A$ a una ciudad 
de destino $B$. Para esto contamos con una serie de vuelos entre distintas 
ciudades entre las que se incluyen $A$ y $B$, 
la idea es encontrar la secuencia de vuelos que logren unir 
la ciudad $A$ con la ciudad $B$ pasando por cualquier 
cantidad de ciudades intermedias, con la restricción de siempre 
respetar una ventana de tiempo entre la llegada a 
la ciudad intermedia y  la salida del próximo vuelo 
(2 horas entre vuelo de llegada hasta la hora de partida del 
siguiente vuelo). Adicionalmente la búsqueda debera 
hacerse en una complejidad menor o igual  a  \Ode{N^2} siendo $N$ 
la cantidad de vuelos.\\

\section{Idea General de la Resoluci\'on}
Modelamos el problema como un multidigrafo en donde los vertices 
son las ciudades y los ejes son los vuelos que conectan las ciudades, en
donde los ejes contendrán como  información la tupla de horario de partida y arribo del vuelo.

La representación del multidigrafo se hará como matriz de ciudades  donde las posiciones $i$ y $j$ son las ciudades origen y destino respectivamente y como valor tiene una lista de viajes desde la ciudad origen  a la destino.
La idea general del algoritmo pasa por modificar un Dijkstra, dado que necesitamos conseguir un camino mínimo donde la función de costo sera la hora de llegada del vuelo y la restricción, que habrá
que agregar al algoritmo, sera la hora de partida. La adaptación de Dijkstra también 
nos permitirá cumplir con el orden de complejidad requerido.
\\

En cada paso del algoritmo(así como Dijkstra) se actualiza un vector de distancias 
, en este caso horario de llegada, a cada una de las ciudades que hasta ahora 
son alcanzables. Si se ira tomando de una lista de ciudades aun no recorridas
y que son alcanzables, pues se encolo un vuelo que llega a esta, y 
se evaluara todos los vuelos que salen desde esa ciudad que cumplen con la
restricción de partir 2 horas después del horario que figura como 
mejor horario de llegada a  la ciudad en la que estamos. \\

Para cada uno de los vuelos salientes que cumplan la restricción
se actualizara en el vector de horario de llegada, 
el mejor horario de llegada en caso de poder mejorarse 
el anterior. Cada vez que se mejora un horario de llegada para una ciudad 
se encola esa ciudad junto con la hora de llegada para ser  procesada
en el paso siguiente o en el que le corresponda según el orden
de la cola que maneja un orden en base a el horario de llegada  a la ciudad.
Se encolaran tuplas con id de ciudad y horario de llegada para en 
cada paso del algoritmo retirar la ciudad a la que se llegue en mejor
horario.\\
La representación del multidigrafo se realizo mediante una matriz de adyacencias.


\subsection{Ejemplos}
Vamos a mostrar dos ejemplo. En el primero es posible construir un camino desde la ciudad A a la ciudad G.
Podemos ver hay dos posibles caminos por los cuales se pueden unir ambas ciudades. El que pasa por la secuencia $A \rightarrowtriangle C \rightarrowtriangle G$ y la secuencia $A \rightarrowtriangle D \rightarrowtriangle F \rightarrowtriangle G$ pero como la primera secuencia llega a las 10 y la otra a las 9, la soluci\'on correcta es la secuencia $A \rightarrowtriangle D \rightarrowtriangle F \rightarrowtriangle G$
\\
\includegraphics[scale=0.7]{imagenes/Ej1_Ejemplo1.png} 
\\
En el segundo ejemplo donde se quiere viajar de la ciudad A a la H, y es un caso en el cual no hay una soluci\'on  posible, como podemos ver si agarramos la ruta de el nodo B o el nodo C no tenemos ning\'un viaje disponible ya que o ya salieron o no cumple con la ventana de tiempo necesaria. para el nodo G, que es el otro viaje posible que tiene A ya el único viaje que tiene ya partió. por lo tanto se concluye que no hay manera de viajar de la ciudad A a la H.
\\
\includegraphics[scale=0.7]{imagenes/Ej1_Ejemplo2.png} 
\\

%\newpage
\subsection{Pseudoc\'odigo}

Aclaraciones sobre variables:
\begin{itemize}
\item $ciudadid$: es el índice que representa la ciudad actual 
(ciudad de origen en el primer paso). En cada paso la ciudad desde la que trato 
de mejorar el vector de horas de llegada va cambiando, y en $ciudadid$  seteo 
la actual.  Nunca se repite la ciudad actual y se procesa a lo sumo 1 vez cada una.

\item
$ciudad$: tupla con la hora de llegada a la ciudad actual, y el id de la ciudad (ciudadid)
\item
$ciudades$: es la matriz  de adyacencia que contiene la lista de vuelos desde la ciudad  $i$ a la ciudad $j$, en la posición $(i,j)$. \\
\item
$visitados$: es el vector que guarda en la posición $i$ la mejor hora de llegada  desde el origen hacia  $i$. Se guarda también desde que ciudad se llega para poder reconstruir el camino y el $i$\\
\item
$ciudadesCant$: cantidad de ciudades del grafo
\item 
$recorridas$: vector con las ciudades que ya se evaluaron como actual.
\end{itemize}

\begin{algorithm}[H]
 \caption{Procesar()}
\COMMENT{Inicializo una cola  que debo recorrer para poder actualizar}
{los mejores horarios de llegada desde ellas hacia el resto,}
{ordenada por menor hora de llegada. La primera ciudad es el origen}
ciudadid = origen\\
\COMMENT{la ciudad 0 es siempre el origen}\\
ciudad = (0,0)\\
seguir = true\\

\WHILE { seguir }
{
\\
	recorridas[ciudadid] = 1
	\COMMENT{me paro en  la ciudad con menor hora de llegada que estaba encolada.} 
	\ForAll{ i = 0 , i $<$ ciudadesCant, i++ }{
		\If{i == ciudadid}{ continuar }
		\ForAll{vuelo en ciudades[ciudadid][i]}{
			\COMMENT{ para cada vuelo entre ciudadid y i, ciudades es la matriz de }
			{adyacencia que guarda la lista de vuelos con sus horarios }
			{vuelo es una tupla con hora de partida y arribo}

			\If{ciudad.llega+2 $<=$ vuelo.sale}{
			\COMMENT{puedo tomar ese vuelo}\\							
				\If{si no tenia registrado hora de llegada a i en visitados, actualizo }{
					visitados[i] = (ciudadid, vuelo.llega, i )
					\COMMENT{como mejore la hora de llegada a i encolo la nueva hora de }
					{llegada a i junto con su padre}\\
					cola.append( ( ciudadid,vuelo.llega,i))
				}
				\COMMENT{si la hora de llegada que tenia a la ciudad de destino }
				{es mayor a la que puedo conseguir entonces reemplazo}
				{por que ahora desde esta ciudad tengo un vuelo que me lleva antes}\\
				\If{ vuelo.llega  $<$ visitados[i][1]}{
					
					visitados[i] = (ciudadid,vuelo.llega,i)					
					\COMMENT{Reemplazo el mejor horario de llegada}
					{Como actualize el mejor horario de llegada a i, encolo i para}
					{que se mejoren los horarios tratando de llegar desde i}
					cola.append( ( ciudadid,vuelo.llega,i))}	
			}		
	}
	}
	\COMMENT{ si no existe ciudades encoladas desde las que recalcular horarios de llegada termine}
	\If{ !cola.size() = 0 }{	
		seguir = false
	}
	\Else{
		\COMMENT{extraigo el minimo de la cola buscando por hora de llegada}
		{y en caso de haber una ciudad en la cola que figura en recorrido}
		{la remuevo. Solo deben quedar las que tienen recorrido[i] = 0 }
		\\
			min = extraerMinimo(cola,recorridos)\\
			ciudadid = min[0]\\
			ciudad = (min[1],min[2])			    
	}
}	
\COMMENT{Cuando se sale del while, en visitados queda }
{para cada ciudad alcanzable el mejor horario de llegada conseguido}
{luego solo resta buscar en ese vector el destino para ver si hay }
{solucion y usando anterior de cada ciudad reconstruir el camino }
\end{algorithm}

\section{Complejidad}

La estructura del algoritmo esta orientada 
desde las ciudades entonces el loop principal lo que ira haciendo 
es parándose en cada una de las ciudades desde el origen y recorriendo
todas las alcanzables para evaluar los vuelos desde la que se encuentre parada 
hacia el resto de las ciudades.\\
De esta manera el while de la linea 6 evaluara en a lo sumo $M$ casos 
siendo $M$ la cantidad de ciudades. \\
La ciudad que este como actual en el while exterior sera el origen 
y se evaluara todos los destinos que tiene y los diferentes vuelos hacia estos.

Luego tenemos un loop interior en el que se entra para todas las ciudades 
hacia las que tenemos vuelos desde la ciudad actual. En el peor 
de los casos cada ciudad estará conectada con $M$ otras ciudades. 
Y para cada una de estas ciudades tendrá $G$ vuelos. Pero aquí 
no puede suceder que M*G sea mayor que $N$ que es la cantidad total de vuelos.\\
En el caso de que $M*G$ sea $N$ tendremos todos los vuelos desde la ciudad actual 
hacia el resto de las ciudades, sin vuelos entre ciudades 
por lo que $M*G$  es $<<=$ que  $N$. Dado que seria un grafo muy particular.

Por lo tanto el loop que comienza antes de la linea 8 y el de la linea 10 no 
podrán ejecutarse en conjunto mas que la cantidad de vuelos totales $N$. 
Dentro de el loop interior desde la linea 11 a la 18 tenemos $K$ operaciones constantes.
Luego al final tenemos que retirar de la lista cual sera la próxima
ciudad que se encuentra mas cerca en horario, a las que ya recorrimos. De 
esta manera siempre voy recorriendo hacia las mas próximas a las que ya recorrí. 
En esta lista saco el minimo y remuevo los vuelos que lleven a ciudades 
ya recorridas por que no podrán mejorar el mejor horario conocido.
Esta operación es lineal en $N$ la cantidad de vuelos. Si que 
dentro del while de la linea 5 tendré una operación $N*K + N$ osea $N*K+1$
operaciones multiplicado por $M$ que es la cantidad de ciudades. 
Esto da un orden de complejidad de $O(N*M*(K+1))$ que es $O(N^2)$


\section{Test de Performance}
El gráfico fue generado con entradas aleatorias para cada $N$ (cantidad de vuelos), las entrada podían o no tener solución. Cada entrada se corrió 100 veces para mitigar el error que pudiera generarse en el computador.\\
\\
\includegraphics[scale=0.7]{imagenes/Ej1.PNG} 
\\
El gr\'afico efectivamente posee un crecimiento $O(N^2)$ con un K constante que fue determinado en $\frac{1}{3000}$. Cambien cabe aclarar que se asumió que en los primero 50 N hubo fluctuaciones que sobrepasaron la cota, pero como a partir de 50 ya no vuelve a pasar el gráfico sigue siendo cota del algoritmo. Fueron calculadas 163 entradas antes que el tiempo ya fuera demasiado prolongado, cada iteración de las 100 tiene una entrada distinta, por lo que se puede afirmar que los tiempos arrojados son promedio para cada N.\\
\section{Ejercicio Adicional}
% El ejercicio adicional propone la inclusion del concepto de aerolinea, y eso a nuestro algoritmo nos modifica en dos cosas, primero nuestra matriz de vuelos tiene que tener a que aerolinea pertenece cada vuelo, y la segunda modificaci\'on  es en el if que comprueba si existe la ventana de tiempo, se le agrega la excepcion de que si el vuelo anterior tiene la misma aerolinea se reduce a 1 la ventana. A costos de complejidad esto no aumenta ni temporal ni espacial ya que la comprobacion de si puedo tomar el viaje sigue siendo $O(1)$ y la estructura sigue siendo $O(N^2)$.  



% El algoritmo original esta pensado con una lógica golosa, en cada paso
% y en base a las  rutas que se conocen desde la ciudad en la que nos
% encontramos ubicados, se mejoran los mejores horarios a los que se 
% puede llegar a las ciudades destino. Esta lógica de valorar
% un vuelo como mejor que otro para llegar a una ciudad de destino 
% en base a el horario de llegada queda invalidada cuando se introduce 
% la excepción de las aerolíneas .\\
La restricción original indicaba que un vuelo no podía 
tomarse antes de las 2 horas de permanencia en la ciudad. 
Esto hace que si con un vuelo se llega a la hora  $X$ 
a una ciudad intermedia, se opte por descartar todos los vuelos
que lleguen a la misma ciudad con hora $X+t$ y $t > 0$.
Ahora para decidir cual es el mejor vuelo que podemos tomar 
desde una ciudad intermedia no nos basta con tener la hora 
en la que llegamos a esa ciudad. Es necesario saber
con cuales aerolíneas se llega a esa hora y si 
es posible llegar con otro vuelo 1 hora mas tarde también. \\
Ahora, por ciudad, la información que necesito 
para evaluar cual es la mejor ruta es una lista de 
horario de llegada y aerolínea. En esta lista los horarios
de llegada no tendrán mas de 1 hora de diferencia. Cualquier 
vuelo que arribe a la ciudad con mas de 1 hora de diferencia
 sera descartado por que cualquiera
sea la  aerolínea no producirá modificaciones 
en la decisión dado que tengo posibilidad de llegar 2 horas antes
que ese vuelo y así la  excepción de la aerolínea no producirá
modificaciones en mi decisión.

En cuanto a los costos de complejidad se modifica el costo
por paso o ciudad que se recorre, al evaluar cuales son las rutas 
que se pueden tomar y cuales no. Antes para cada vuelo 
saliente desde una ciudad teníamos un solo valor de referencia. Ahora
tenemos una lista de aerolíneas que llegan a la ciudad 1 hora
después que el mejor vuelo para esa ciudad. En el peor de los
casos podre tener $n-2$ vuelos en esa lista ( por ej: ciudades
$A$ $B$ y $C$ $n-1$ vuelos de $A$ a $B$ y 1 vuelo de $C$ )
que tendré que evaluar para ver si puedo tomar alguno de los 
vuelos salientes desde la ciudad que estoy. 
Este checkeo agregara un costo lineal al $O(n^2)$ original del problema
resultando en una nueva complejidad de $O(n^3)$.


\section{Codigo fuente}

\begin{verbatim}
	
void Ej1::Procesar(){
	// (ciudad origen, hora llegada, ciudad destino)
	forward_list<  tuple<string, unsigned int, string> > cola;	
	tuple<string, unsigned int, string> a = make_tuple(origen, 0, origen);	
	visitados.clear();
	for (map < string, map < string, vector< pair<unsigned int, unsigned int> > > >::iterator it = ciudades.begin(); 
		it != ciudades.end(); 
		++it) {
		visitados.insert(make_pair(it->first, make_tuple("-1", -1, -1))); 
	}
	visitados[origen] = make_tuple("", 0, 0);
	map<string,int> recorridos;	
	set<string>::iterator it;	

	forward_list< tuple<string, unsigned int, string> >::iterator rm,min,colaIt,colaItPrev;	

	bool seguir = true;
	while (seguir)
	{
		
		string ciudadid = get<2>(a);
		recorridos[ciudadid] = 1;
		unsigned int horallegada = get<1>(a);
		//unsigned int origen = get<0>(a);

		for (map < string, map < string, vector< pair<unsigned int, unsigned int> > > >::iterator ciudadesIt = ciudades.begin(); ciudadesIt != ciudades.end(); ++ciudadesIt)
		{
			string i = ciudadesIt->first;
			if (i == ciudadid)
				continue;

			for (unsigned int v = 0; v < ciudades[ciudadid][i].size(); v++)
			{
				unsigned int sale = get<0>(ciudades[ciudadid][i][v]);
				unsigned int llega = get<1>(ciudades[ciudadid][i][v]);
				
				if ( ciudadid == origen || (horallegada <= (sale + 2)))  
				{
					//puedo tomar ese vuelo
					if ((get<0>(visitados[i]) == "-1") && (get<1>(visitados[i]) == -1) && 
						(get<2>(visitados[i]) == -1))
					{
						visitados[i] = make_tuple(ciudadid, sale, llega);
						cola.push_front(make_tuple(ciudadid, llega, i));
					}
					if (  llega < (unsigned int)get<2>(visitados[i]))
					{
						visitados[i] = make_tuple(ciudadid, sale, llega);
						cola.push_front(make_tuple(ciudadid, llega, i));
					}
				}
			}

		}
		
		if (!cola.empty())
		{
			colaIt =  cola.begin();
			
			int t = 0;
			do{
				//remuevo los vuelos que van a ciudades que  ya recorridos
				if ( recorridos[ get<2>(*colaIt) ] == 1){
					if (t ==0 ){
						cola.pop_front();
						colaIt = cola.begin();
					}else{
						cola.erase_after(colaItPrev);
						colaIt = colaItPrev;
						colaIt ++;
					}
				}else{
					if (t == 0 ||  get<1>(*min)> get<1>(*colaIt) ){
						min = colaIt;
					}
					colaItPrev = colaIt;
					colaIt++;
					t++;
				}
				

			}while( !cola.empty()  && colaIt != cola.end() );
			if (!cola.empty()){
				a = *min;
			}else{
				seguir = false;
			}
		}
		else
		{
			seguir = false;
		}
	}


\end{verbatim}